A. Field of the Invention
The present invention relates to a method and an apparatus for displaying a 3D object such as an equi-valued surface (iso-surface) on the basis of the graphics data of polygons, and more particularly to a method and a system for the execution of types of 3D object processing such as hidden surface removal that are done in order of the depth of polygons, without performing depth calculations for polygons or polygon sorting.
B. Prior Art
A depth sorting algorithm and a z-buffer algorithm are typical examples of conventional methods for approximating a 3D object such as equi-valued surface to polygons and performing hidden surface processing on the polygonal data in order of depth. The depth sorting algorithm requires depth calculations for all the polygons and sorts them in order of depth, so there is a problem that a long time is required to sort the large number of polygons making up a complex object. In contrast, the z-buffer algorithm needs no sorting, but it requires a large amount of memory to store the depth of each pixel, and cannot display transparent objects. Moreover, depth calculation must be performed for each polygon.
Japanese Published Unexamined Patent Application No. 60-198690 discloses a method for improving depth-sorting algorithms. In accordance with this method, a space that contains polygons is divided into a plurality of blocks after polygonal data are generated and stored. Then, after the position of a view point has been determined, the depth of each block from the view point is calculated. A complicated calculation using a graph where the blocks are represented by nodes and their boundaries by branches is used for the depth calculations. The blocks are sorted in order of the calculated depths. In each block, on the other hand, the depths of polygons are calculated, and the polygons are sorted in order of depth. When an object is displayed, polygonal data are taken out sequentially from the block furthest from the view point. Polygons contained in the same block are displayed in order of depth. This reduction in the number of polygons to be sorted shortens the sorting process.
However, it is not a thorough solution in that depth calculation is required for all the polygons, and polygon sorting is required even if depth calculation is carried out for each block. In addition, the method for determining the depth order of the blocks is complicated, which causes a new problem that the required processing time and memory size are not negligible.